
\section{随机数的期望值与方差}
如果一个随机变量 $X$ 的概率密度为 $f(x)$（不失一般性，离散分布的随机数可以用带有 $\delta$ 函数的 $f(x)$ 描述），则其期望值为
\begin{eqnarray}
E(X) = \int^\infty_{-\infty} x f(x) dx,
\end{eqnarray}
其方差为
\begin{eqnarray}
D(X) = \int^\infty_{-\infty} ( x - E(X) )^2 f(x) dx.
\end{eqnarray}

如果相互独立的随机变量 $X_1, X_2, \cdots, X_n$ 的概率密度分别为 $f_1(x), f_2(x), \cdots, f_n(x)$，那么 $X_1 + \cdots + X_n$ 的期望和方差分别是多少？
\begin{eqnarray}
E(X_1 + \cdots X_n) &=& \int dx_1 \int dx_2 \cdots \int dx_n f_1(x_1) f_2(x_2) \cdots f_n(x_n) (x_1 + x_2 +\cdots x_n) \nonumber\\
&=& \sum^n_{i=1} \int dx_1 \int dx_2 \cdots \int dx_n f_1(x_1) f_2(x_2) \cdots f_n(x_n) x_i \nonumber\\
&=& E(X_1) + \cdots E(X_n) \nonumber\\
D(X_1 + \cdots X_n) &=& \int dx_1 \int dx_2 \cdots \int dx_n (x_1 + x_2 + \cdots + x_n - E(X_1 + \cdots + X_n))^2 \nonumber\\
															&& \times f_1(x_1) f_2(x_2) \cdots f_n(x_n) dx_1 dx_2 \cdots dx_n \nonumber\\
												&=& \int dx_1 \int dx_2 \cdots \int dx_n \left[ (x_1-E(X_1)) + (x_2 - E(X_2)) + \cdots + (x_n - X_n) \right]^2 \nonumber\\
															&& \times f_1(x_1) f_2(x_2) \cdots f_n(x_n) dx_1 dx_2 \cdots dx_n \nonumber\\
												&=& D(X_1) + D(X_2) + \cdots D(X_n)
\label{EDsum}
\end{eqnarray}

如果一个随机变量 $X$ 的概率密度函数为 $f(x)$，$\lambda$ 为一个正实数，那么 $\lambda X$ 的概率密度、期望与方差分别是多少？
\begin{eqnarray}
P\left\{ \lambda X \leq \alpha \right\} = P\left\{ X \leq \frac{\alpha}{\lambda} \right\} = \int^\frac{\alpha}{\lambda}_{-\infty} f(x) dx,
\end{eqnarray}
所以 $\lambda X$ 的概率密度函数为
\begin{eqnarray}
g(\alpha) = \frac{d}{d\alpha} P\left\{ \lambda X \leq \alpha \right\} = \frac{d}{d\alpha} \int^\frac{\alpha}{\lambda}_{-\infty} f(x) dx = \frac{1}{\lambda} f(\alpha/\lambda).
\end{eqnarray}
$\lambda X$ 的期望值为
\begin{eqnarray}
E(\lambda X) = \int^\infty_{-\infty} \frac{\alpha}{\lambda} f(\alpha/\lambda) d\alpha = \lambda E(X),
\label{ElambdaX}
\end{eqnarray}
$\lambda X$ 的方差为
\begin{eqnarray}
D(\lambda X) &=& \int^\infty_{-\infty} \left[\alpha - E(\lambda X)\right]^2 \frac{1}{\lambda} f(\alpha/\lambda) d\alpha \nonumber\\
				&=& \int^\infty_{-\infty} \left[\alpha - \lambda E(X) \right]^2 \frac{1}{\lambda} f(\alpha/\lambda) d\alpha \nonumber\\
				&=& \lambda^2 \int^\infty_{-\infty} \left[ \frac{\alpha}{\lambda} - E(X)\right]^2 f(\alpha/\lambda) d \frac{\alpha}{\lambda} \nonumber\\
				&=& \lambda^2 D(X)
\label{DlambdaX}
\end{eqnarray}

\section{大数定律与中心极限定理}
蒙特卡洛方法的理论依据是概率论中的大数定律与中心极限定理。
根据大数定律，随机抽样的统计平均会逼近理论预期；而中心极限定理可以用来估算抽样结果的误差。
所以这里简述这两个定理的证明，如果需要更多细节，请参考\cite{ProbabilityTheory}。

\subsubsection{切比雪夫（Chebyshev）不等式}

设随机变量 $X$ 的期望 $E(x)$ 和 方差 $D(x)$ 都存在，则 $\forall \epsilon>0$，都有切比雪夫不等式：
\begin{eqnarray}
P\left\{ | X - E(X) | \leq \epsilon \right\} \geq 1- \frac{ D(X) }{ \epsilon^2}
\end{eqnarray}
证明：假设概率密度函数为 $f(x)$，则有
\begin{eqnarray}
P\left\{ | X - E(X) | \geq \epsilon \right\} &=& \int_{ | X - E(X) | \geq \epsilon} f(x) dx \nonumber\\
				&\leq& \int_{ | X - E(X) | \geq \epsilon} \frac{ \left[x- E(X)\right]^2 }{\epsilon^2} f(x) dx \nonumber\\
				&\leq& \frac{1}{\epsilon^2} \int^\infty_{-\infty} (x- E(X))^2 f(x) dx \nonumber\\
				&=& \frac{ D(X) }{ \epsilon^2}.
\end{eqnarray}
所以
\begin{eqnarray}
P\left\{ | X - E(X) | \leq \epsilon \right\} = 1- P\left\{ | X - E(X) | \geq \epsilon \right\}
 \geq 1- \frac{ D(X) }{ \epsilon^2}，
\end{eqnarray}
即证明了切比雪夫不等式。

\subsubsection{切比雪夫大数定律}

设独立随机变量 $X_1, X_2, \cdots, X_n, \cdots$ 具有相同的数学期望和方差，$E(X_i)=\mu, D(X_i) = \sigma^2 (i=1,2,\cdots)$，则 $\forall \epsilon$，有
\begin{eqnarray}
\lim_{n \rightarrow \infty} P \left\{ | \frac{1}{n} \sum\limits^n_{i=1} X_i - \mu | \leq \epsilon \right\} =1.
\label{large_number_theorem}
\end{eqnarray}
证明：根据公式（\ref{EDsum}-\ref{DlambdaX}），
\begin{eqnarray}
E( \frac{1}{n} \sum \limits^n_{i=1} X_i ) &=& \mu, \nonumber\\
D( \frac{1}{n} \sum \limits^n_{i=1} X_i) &=& \frac{ \sigma^2}{n}
\end{eqnarray}
所以，根据切比雪夫不等式，$\forall \epsilon >0$,
\begin{eqnarray}
P\left\{ | \frac{1}{n} \sum\limits^n_{i=1} X_i - \mu | \leq \epsilon \right\} \geq 1- \frac{ \sigma^2 }{ n \epsilon^2},
\end{eqnarray}
所以
\begin{eqnarray}
\lim_{n \rightarrow \infty} P \left\{ | \frac{1}{n} \sum\limits^n_{i=1} X_i - \mu | \leq \epsilon \right\}
\geq \lim_{n \rightarrow \infty} \left[1- \frac{ \sigma^2 }{ n \epsilon^2} \right]
 =1.
\end{eqnarray}
这个数不可能超过1，所以它的极限必等于1。这样，我们就证明了切比雪夫大数定律。

在实践中，我们每次抽样的结果都是随机的，有一个概率分布和确定的期望、方差；切比雪夫大数定律意味着，随着抽样次数增多，抽样结果的统计平均必然收敛于每次抽样的期望值。

\subsubsection{中心极限定理}
{\bf 独立同分布的中心极限定理}：假设随机变量 $X_1, \cdots X_n$ 相互独立且遵循同一分布，期望值为 $\mu$，方差为 $\sigma^2$，则
\begin{eqnarray}
\lim_{n \rightarrow \infty} \frac{ \sum\limits^n_{i=1} X_i - n \mu }{ \sqrt{n} \sigma } \sim N(0,1),
\label{central_limit_theorem}
\end{eqnarray}
其中 $N(0,1)$ 表示期望为 $0$，方差为 $1$ 的正态分布。这是一个美妙的定理，因为它不依赖于 $X_i$ 的具体概率密度函数。它说明正态分布是大自然的选择。

为了证明这个定理，我们先简单介绍概率论中所谓“特征函数”：如果一个随机变量 $X$ 的概率密度函数为 $f(x)$，则其特征函数为 $\varphi_X (t) = \int^\infty_{-\infty} e^{i t x } f(x) dx$，即正比于概率密度函数的傅里叶变换。
如果一个随机变量的概率密度函数确定了，其特征函数也唯一确定，反之亦然，所以特征函数也反映了随机变量的性质。
例如，特征函数 $\varphi_X(t)$ 的一阶导数、二阶导数在 $t=0$ 处的值反映了随机变量 $X$ 的期望和方差。
\begin{eqnarray}
\frac{d}{dt} \varphi_X(t)|_{t=0} &=& \frac{d}{dt} \int^\infty_{-\infty} e^{i t x} f(x) dx |_{t=0} \nonumber\\
																	&=& \int^\infty_{-\infty} i x f(x) dx = i E(X) \nonumber\\
\frac{d^2}{dt^2} \varphi_X(t)|_{t=0} &=& - \int^\infty_{-\infty} x^2 f(x) dx = - D(X) - E(X)^2
\label{characteristic_derivative}
\end{eqnarray} 
正态分布 $N(0,1)$ 的概率密度函数为
\begin{eqnarray}
f_{N(0,1)}(x) = \frac{1}{ \sqrt{2\pi} } e^{-\frac{x^2}{2}},
\end{eqnarray}
其特征函数为
\begin{eqnarray}
\varphi_{N(0,1)}(t) &=& \int^\infty_{-\infty} \frac{1}{\sqrt{2\pi}} e^{ - \frac{x^2}{2} + itx}dx = e^{-\frac{1}{2} t^2}.
\label{characteristic_normal_distribution}
\end{eqnarray}
最后一步用了泊松积分，如果你感兴趣，可以参考\cite{Calculus4}第123页。
值得注意，$f_{N(0,1)}(x)$ 与 $\varphi_{N(0,1)}(t)$ 具有相同的形式，具有对称的美。

此外，如果 $X_1, X_2$ 是相互独立的随机变量，其概率密度函数分别为 $f(x), g(x)$，则 $X_1 + X_2$ 的概率密度函数为
\begin{eqnarray}
h(x) &=& \frac{d}{dx} \int^\infty_{-\infty} d \xi f(\xi)  \int^{ x- \xi}_{-\infty} g(\eta) d\eta = \int^\infty_{-\infty} f(\xi) g(x-\xi) d\xi,
\end{eqnarray}
其傅里叶展开为
\begin{eqnarray}
\varphi_{X_1 + X_2} (t) = \int^\infty_{-\infty} \int^\infty_{-\infty} f(\xi) g(x-\xi) d\xi e^{itx} dx = \varphi_{X_1}(t) \varphi_{X_2}(t).
\end{eqnarray}
这个结论很容易推广到 $n$ 个独立随机变量的和，即
\begin{eqnarray}
\varphi_{X_1 + \cdots X_n} = \varphi_{X_1}(t) \cdots \varphi_{X_n}(t).
\label{characteristic_sum}
\end{eqnarray}

下面我们证明独立同分布中心极限定理，即公式（\ref{central_limit_theorem}），这个思路来自\cite{wiki}中``central limit theorem”词条，略有修改。
记
\begin{eqnarray}
Z_n = \frac{ \sum\limits^n_{i=1} X_i - n \mu }{ \sqrt{n} \sigma } = \sum\limits^n_{i=1} Y_i,
\end{eqnarray}
其中 $Y_i \equiv  \frac{1}{\sqrt{n}} \frac{X_i - \mu}{\sigma}$，根据公式（\ref{EDsum}-\ref{DlambdaX}），显然 $E(Y_i)=0, D(Y_i)=\frac{1}{n}$。
根据公式（\ref{characteristic_sum}），$Z_n$ 的特征函数为
\begin{eqnarray}
\varphi_{Z_n}(t) = \varphi_{Y_1}(t) \cdots \varphi_{Y_n}(t) = \varphi_{Y_1}(t) ^n.
\end{eqnarray}
根据公式（\ref{characteristic_derivative}），我们有
\begin{eqnarray}
\varphi_{Z_n}(t) = \varphi_{Y_1}(t)^n &=& \left\{ 1 + iE(Y_1)t - \frac{1}{2} \left[ D(Y_1) + E(Y_1)^2 \right] t^2 + \cdots \right\}^n \nonumber\\
									&=& \left\{ 1 - \frac{1}{2n} t^2 + \cdots \right\}^n
\end{eqnarray}
故 $n\rightarrow \infty$ 时，有
\begin{eqnarray}
\lim_{n \rightarrow \infty} \varphi_{Z_n}(t) &=& \lim_{n \rightarrow \infty}  \left\{ 1 - \frac{1}{2n} t^2 + \cdots \right\}^n \nonumber\\
																							&=& e^{-\frac{1}{2}t^2}
\end{eqnarray}
比较上式与公式（\ref{characteristic_normal_distribution}），可知
\begin{eqnarray}
\lim_{n \rightarrow \infty} \frac{ \sum\limits^n_{i=1} X_i - n \mu }{ \sqrt{n} \sigma } \sim N(0,1),
\end{eqnarray}
这样我们便证明了独立同分布的中心极限定理。
